1. Field of the Invention
The invention relates to the field of wireless communications, and specifically the invention relates to a method for dynamically allocating time slots of a common time division multiple access (TDMA) broadcast channel to a network of transceiver nodes.
2. Description of the Prior Art
A packet radio network consists of a number of geographically dispersed transceiver nodes that communicate with each other. Due to limited transmission power and the geographic distance that physically separates the nodes, the transmissions of a given node cannot be received by every other node in the network. Instead, the transmissions of a given node can be received only by the nodes located within the circular area covered by its transmission range R. Referring to FIG. 1, the transmissions of node n can be received only by the radios located within a circle 10 whose radius is equal to R, and its center is the location of node n. The circular area covered by the transmission range R of a node is referred to as the node's one-hop neighborhood. The circle 10 having node n as its center and R as its radius is the boundary of node n's one-hop neighborhood. Similarly, the circle 14 having node j as its center and R as its radius is the boundary of node j's one-hop neighborhood.
The circular area bounded by the circle 12 whose radius is equal to two times the transmission range (2R) and has node n as its center is defined as node n's two-hop neighborhood. Node n's two-hop neighborhood includes all the nodes that are included in the one-hop neighborhoods of all its one-hop neighbors. A node located within another node's one-hop neighborhood is referred to as a one-hop neighbor. Similarly, a node located within another node's two-hop neighborhood is referred to as a two-hop neighbor. The number of a node's one-hop neighbors is defined as the node degree. The maximum node degree of a network at a particular time instant is defined as the network degree. The maximum node degree of a network over all time is defined as the maximum network degree. In the rest of this specification, whenever a neighbor is not specified as ‘one-hop’ or ‘two-hop’ it will be understood that it is a one-hop neighbor.
The problem of dynamically allocating the time slots of a common TDMA broadcast channel to a geographically dispersed network of mobile transceiver nodes is especially challenging, this is because the time slot allocation in such an environment has to maximize the spatial re-use of time slots, while at the same time guaranteeing that each node's broadcast transmissions are successfully received by all its one-hop neighbors. In order to guarantee that a given node's broadcast transmissions during a given time slot are successfully received by all its one-hop neighbors, that node has to be the only transmitter within its two-hop neighborhood during that time slot.
With continued reference to FIG. 1, if nodes n and j transmit during the same time slot their transmissions will collide at node k, which is a one-hop neighbor of both nodes n and j. Therefore, in order to guarantee that node n's broadcast transmissions are successfully received by all its one-hop neighbors, node n has to be the only transmitter in its two-hop neighborhood, which is the area bounded by circle 12. The objective of an efficient TDMA time slot allocation method is to maximize the number of nodes that can transmit during the same time slot, while at the same time guaranteeing that their one-hop neighborhoods do not overlap. Furthermore, such a TDMA time slot allocation has to be resilient to changes in connectivity (topology) that are caused by the constant mobility of the network transceiver nodes.
Proposed TDMA time slot allocation methods can be divided into two categories: topology-dependent and topology-transparent. Topology-dependent time slot allocation methods rely on the instantaneous connectivity between the nodes within a two-hop neighborhood, and dynamically re-allocate time slots in a distributed manner in response to connectivity changes.
The main disadvantage of topology-dependent TDMA time slot allocation methods is that their efficiency and robustness is vulnerable in a highly mobile environment for the following reasons:    a) Significant overhead may be incurred in the process of coordinating time slot re-allocation within a two-hop neighborhood, due to the exchange of control packets that is required in order for all nodes involved in the re-allocation to have a consistent view of the updated time slot allocation;    b) Depending on the timing of events and the particular connectivity, the time slot re-assignment process within a two-hop neighborhood may trigger time slot re-assignments in adjacent, overlapping two-hop neighborhoods, causing a time slot re-allocation ‘ripple’ effect that could propagate throughout the entire network; this would increase the control overhead required to synchronize all the nodes even more;    c) Transmissions are lost during the transient period of time slot re-allocation; lost transmissions can seriously degrade network performance during transient periods since they cause retransmissions to occur, which in turn will be lost again if the time slot reallocation process has not converged, causing further retransmissions; in other words, if the transient period of the time slot re-allocation process is longer than some critical time threshold, the network performance may experience a spiral degradation;    d) The time slot re-allocation process may never converge if the rate of topology change exceeds the rate at which the protocol can re-compute and distribute the new schedules; this will cause catastrophic failure of the network.
In order to overcome the above deficiencies, a number of topology-transparent time slot allocation methods have been proposed. The basic idea of the proposed topology-transparent time slot allocation methods is for a node to transmit in a number of time slots in each time frame. The time slots which node n is allocated in a time frame correspond to a unique code such that for any given one-hop neighbor k of node n, node n is allocated at least one time slot which is not allocated to node k or any of k's one-hop neighbors. Therefore, within any given time frame, any neighbor of n can receive at least one packet from n collision-free.
The disadvantages of the topology-transparent TDMA time slot allocation methods are the following:    a) The transmitter is unable to know which neighboring nodes can correctly receive the packet it sends in a particular slot, because these methods cannot guarantee a unique transmitter within a two-hop neighborhood; therefore, these time slot allocation methods cannot be used in conjunction with interactive query/response schemes between a particular transmitter and a particular receiver. In addition, since the transmitter does not know which neighbor can receive its transmissions at what time slot, it has to repeat transmitting the same packet during every allocated time slot within a frame in order to guarantee that the intended destination correctly receives the packet.    b) The number of time slots between successive transmissions of different packets by a given node produced by these methods is proportional to the square of the maximum network degree; therefore, the bandwidth efficiency of these methods drops exponentially as the maximum network degree increases.    c) They require a priori knowledge of the network size and the maximum network degree; therefore, these methods cannot be used in scenarios where the network size and the maximum network degree vary in an unpredictable manner.
A need therefore exists for a distributed, dynamic TDMA time slot allocation method that overcomes the limitations of the prior art TDMA time slot allocation methods in mobile, geographically dispersed, broadcast packet radio networks.